package com.zp.self.module.level_4_算法练习.算法.广度优先搜索;

import com.zp.self.module.level_4_算法练习.数据结构.二叉树.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @author By ZengPeng
 */
public class 力扣_637_二叉树的层平均值 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_637_二叉树的层平均值().averageOfLevels(TreeNode.initRoot()));
    }

    /**
    题目：给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。
     与实际答案相差 10-5 以内的答案可以被接受。

     示例 1：
     输入：root = [3,9,20,null,null,15,7]
     输出：[3.00000,14.50000,11.00000]
     解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
     因此返回 [3, 14.5, 11] 。

     示例 2:
     输入：root = [3,9,20,15,7]
     输出：[3.00000,14.50000,11.00000]

    分析：【P 💖💝】
       1.广度优先遍历：一个Queue 记录当前层，一个Queue 记录下一层，遍历完后互换
            --执行用时：3 ms, 在所有 Java 提交中击败了25.87%的用户
       2.优化Queue 为 List: 避免了进栈、出栈的维护，所以加快了速度？ 得看看源码才能分析
            --执行用时：2 ms, 在所有 Java 提交中击败了94.53%的用户
       3.再度优化:深度优先遍历  记录每层的个数List<Integer> ,记录每层的总和
            -- 好强啊
    边界值 & 注意点：
       1.
     **/
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        List<TreeNode> parent = new ArrayList<>();
        List<TreeNode> childes;
        parent.add(root);
        while (!parent.isEmpty()){
            double sum = 0d;
            childes = new ArrayList<>();
            for (TreeNode treeNode : parent) {
                if (treeNode.left != null)
                    childes.add(treeNode.left);
                if (treeNode.right != null)
                    childes.add(treeNode.right);
                sum += treeNode.val;
            }
            res.add(sum/parent.size());
            parent = childes;
        }
        return  res;
    }

    private void bfs(TreeNode root, List<Double> res, Queue queue) {
        if(root==null) return;


    }
}
